#include "point.h"
#include <iostream>
#include <algorithm>

point::point()
{}

point::point(double x_, double y_) : x(x_), y(y_)
{
}

sign long_left_turn(const point &p1, const point &p2, const point &p3)
{
    mpq_class p1x = p1.x; mpq_class p1y = p1.y;
    mpq_class p2x = p2.x; mpq_class p2y = p2.y;
    mpq_class p3x = p3.x; mpq_class p3y = p3.y;

    mpq_class res = (p3x - p1x) * (p2y - p1y) - (p3y - p1y) * (p2x - p1x);

    if (res < 0)
        return NEGATIVE;
    else if (res > 0)
        return POSITIVE;
    else
        return EQUAL;
}

sign left_turn(const point& p1, const point& p2, const point& p3)
{
    double tmp1 = (p3.x - p1.x) * (p2.y - p1.y);
    double tmp2 = (p3.y - p1.y) * (p2.x - p1.x);
    double res = tmp1 - tmp2;
    double eps = meps * (std::abs(tmp1) + std::abs(tmp2));

    if (res < -eps)
        return NEGATIVE;
    else if (res > eps)
        return POSITIVE;
    else
        return long_left_turn(p1, p2, p3);
}

std::istream& operator >>(std::istream& in, point& p)
{
    double x, y;
    in >> x >> y;
    p = point(x, y);
    return in;
}

std::ostream& operator <<(std::ostream& out, const point& p)
{
    return out << p.x << " " << p.y;
}


bool point::operator == (const point& other)
{
    return (x == other.x) && (y == other.y);
}


bool point::operator != (const point& other)
{
    return !(*this == other);
}

sign long_in_circle(const point& a, const point& b, const point& c, const point& p)
{
    mpq_class ax = a.x; mpq_class ay = a.y;
    mpq_class bx = b.x; mpq_class by = b.y;
    mpq_class cx = c.x; mpq_class cy = c.y;
    mpq_class px = p.x; mpq_class py = p.y;

    mpq_class det1 = (ax - px) * (by - py) * ((cx * cx - px * px) + (cy * cy - py * py));
    mpq_class det2 = (ay - py) * (cx - px) * ((bx * bx - px * px) + (by * by - py * py));
    mpq_class det3 = (bx - px) * (cy - py) * ((ax * ax - px * px) + (ay * ay - py * py));

    mpq_class det4 = (cx - px) * (by - py) * ((ax * ax - px * px) + (ay * ay - py * py));
    mpq_class det5 = (bx - px) * (ay - py) * ((cx * cx - px * px) + (cy * cy - py * py));
    mpq_class det6 = (ax - px) * (cy - py) * ((bx * bx - px * px) + (by * by - py * py));

    mpq_class det = det1 + det2 + det3 - det4 - det5 - det6;

    if (det < 0)
        return OUT;
    if (det > 0)
        return INSIDE;
    return BOUND;
}

//copypast from Shewchuck
sign in_circle(const point& a, const point& b, const point& c, const point& d)
{
  double adx, bdx, cdx, ady, bdy, cdy;
  double bdxcdy, cdxbdy, cdxady, adxcdy, adxbdy, bdxady;
  double alift, blift, clift;
  double det;
  double permanent, errbound;

  adx = a.x - d.x;
  bdx = b.x - d.x;
  cdx = c.x - d.x;
  ady = a.y - d.y;
  bdy = b.y - d.y;
  cdy = c.y - d.y;

  bdxcdy = bdx * cdy;
  cdxbdy = cdx * bdy;
  alift = adx * adx + ady * ady;

  cdxady = cdx * ady;
  adxcdy = adx * cdy;
  blift = bdx * bdx + bdy * bdy;

  adxbdy = adx * bdy;
  bdxady = bdx * ady;
  clift = cdx * cdx + cdy * cdy;

  det = alift * (bdxcdy - cdxbdy)
      + blift * (cdxady - adxcdy)
      + clift * (adxbdy - bdxady);

  permanent = (abs(bdxcdy) + abs(cdxbdy)) * alift
            + (abs(cdxady) + abs(adxcdy)) * blift
            + (abs(adxbdy) + abs(bdxady)) * clift;
  double epsilon = std::numeric_limits<double>::epsilon();
  double iccerrboundA = (10.0 + 96.0 * epsilon) * epsilon;
  errbound = iccerrboundA * permanent;

  if (det < -errbound)
      return OUT;
  if (det > errbound)
      return INSIDE;
  else
      return long_in_circle(a, b, c, d);
}

sign long_in_circle(const point& a, const point& b, const point& p)
{
    mpq_class ax = a.x; mpq_class ay = a.y;
    mpq_class bx = b.x; mpq_class by = b.y;
    mpq_class px = p.x; mpq_class py = p.y;

    mpq_class scal = (px - ax) * (px - bx) + (py - ay) * (py - by);

    if (scal > 0)
        return OUT;
    if (scal < 0)
        return INSIDE;
    return BOUND;
}

sign in_circle(const point& a, const point& b, const point& p)
{
    double tmp1 = (p.x - a.x) * (p.x - b.x);
    double tmp2 = (p.y - a.y) * (p.y - b.y);

    double eps = meps * (std::fabs(tmp1) + std::fabs(tmp2));

    double scal = tmp1 + tmp2;


    if (scal > eps)
        return OUT;
    else if (scal < -eps)
        return INSIDE;
    else
        return long_in_circle(a, b, p);
}

sign in_circle(const std::vector<point>& points, const point& p)
{
    if (points.size() == 2)
        return in_circle(points[0], points[1], p);
    else
        return in_circle(points[0], points[1], points[2], p);
}

sign in_circle(const std::vector<point>::iterator begin, const size_t size, const point& p)
{
    if (size == 2)
        return in_circle(*begin, *(begin + 1), p);
    else
        return in_circle(*begin, *(begin + 1), *(begin + 2), p);
}

/*std::vector<point> circumscribed_circle(const std::vector<point>& points)
{
    std::vector<point> result = {points[0], points[1]};
    for (size_t i = 2; i < points.size(); i++)
    {
        if (in_circle(result, points[i]) != OUT)
            continue;
        result = {points[i], points[0]};
        for (size_t j = 1; j < i; j++)
        {
            if (in_circle(result, points[j]))
                continue;
            result = {points[i], points[j]};
            for (size_t k = 0; k < j; k++)
            {
                if (in_circle(result, points[k]))
                    continue;
                result = {points[i], points[j], points[k]};
            }
        }
    }

    return result;
}*/

//[что видим] (аргументы) {return ...; };

template<typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v)
{
    out << "[";
    for (auto x : v)
        out << x << ", ";
    return out << "]";
}

std::vector<point> circumscribed_circle(std::vector<point> points)
{
    size_t i = 2;
    size_t answer_size = 2;
    auto peek = [&points] (size_t size) {
        return std::vector<point>(points.begin(), points.begin() + size);
    };
    while (i < points.size())
    {
        for (;in_circle(peek(answer_size), points[i]) != OUT; i++);
        std::swap(points[i], points[answer_size]);
        std::rotate(points.begin(), points.begin() + answer_size - 1, points.begin() + answer_size);
        i = answer_size = in_circle(peek(2), points[2]) != OUT ? 2 : 3; 
    }

    return peek(answer_size);
}

